package algo.LocalSearch;

import algo.Model.BasicLocalSearchEntity;
import algo.Model.VarInt;
import java.util.*;

public class Alldifferent extends BasicLocalSearchEntity implements IConstraint {
	VarInt[]	_x;
	int			_violations;
	int			_minValue;
	int			_maxValue;
	int[]		_occ;//_occ[v-_minValue] is the number of occurrences of value v in _x
	HashMap<VarInt,Integer>		_map; // _map[z] is the index of variable z in the array _x[...]
	public Alldifferent(VarInt[] x){
		_x = x;
		post();
	}
	
	void post(){
		_minValue = _x[0].getMinValue();
		_maxValue = _x[0].getMaxValue();
		for(int i = 1; i < _x.length; i++){
			VarInt y = _x[i];
			if(_minValue > y.getMinValue()) _minValue = y.getMinValue();
			if(_maxValue < y.getMaxValue()) _maxValue = y.getMaxValue();
		}
		_occ = new int[_maxValue-_minValue+1];
		for(int v = _minValue; v <= _maxValue; v++){
			_occ[v-_minValue] = 0;
		}
		
		_map = new HashMap<VarInt,Integer>();
		for(int i = 0; i < _x.length; i++){
			_map.put(_x[i], i);
		}
	}
	
	public BasicLocalSearchEntity[] getDependEntities(){
		return _x;
	}
	
	public String name(){
		return "NotEqual[" + getID() + "]";
	}
	
	public VarInt[] getVariables(){ return _x;}
	@Override
	public int violations() {
		// TODO Auto-generated method stub
		return _violations;
	}

	@Override
	public int getAssignDelta(VarInt x, int val) {
		//System.out.println("Alldiffferent::getAssignDelta(x," + val + ")");
		// TODO Auto-generated method stub		
		int newV = violations();
		int idx = (int)_map.get(x);// the index of x in the array _x[...]
		if(idx < 0 || idx >= _x.length)
			return 0;// variable x does not participate to the constraint
		int v = _x[idx].getValue();// current value of x
		if(v == val) return 0;
		int v1 = v - _minValue;
		
		if(_occ[v1] > 1) newV--;
		if(val < _minValue || val > _maxValue){
			System.out.println("Alldifferent::getAssignDelta, value " + val + " is out of bound of variables");
			assert(false);
		}
		int v2 = val - _minValue;
		if(_occ[v2] >= 1)
			newV++;
		return newV - violations();
	}

	@Override
	public void propagateInt(VarInt x, int val) {
		// TODO Auto-generated method stub
		int idx = (int)_map.get(x);// the index of x in the array _x[...]
		if(idx < 0 || idx >= _x.length)
			return ;// variable x does not participate to the constraint
		int v = _x[idx].getValue();// current value of x
		if(v == val) return ;
		int v1 = v - _minValue;
		
		if(_occ[v1] > 1) _violations--;
		if(val < _minValue || val > _maxValue){
			System.out.println("Alldifferent::getAssignDelta, value " + val + " is out of bound of variables");
			assert(false);
		}
		int v2 = val - _minValue;
		if(_occ[v2] >= 1)
			_violations++;
		
		_occ[v1]--;
		_occ[v2]++;
	}

	@Override
	public void initPropagate() {
		// TODO Auto-generated method stub
		for(int i = 0; i < _x.length; i++){
			int v = _x[i].getValue();
			_occ[v-_minValue]++;
		}
		_violations = 0;
		for(int v = _minValue; v <= _maxValue; v++){
			int idx = v - _minValue;
			if(_occ[idx] > 1)
				_violations += _occ[idx] - 1;
		}
	}

	@Override
	public boolean verify() {
		// TODO Auto-generated method stub
		// recompute occ and violations
		int[] occ = new int[_maxValue - _minValue + 1];
		for(int v = _minValue; v <= _maxValue; v++)
			occ[v-_minValue] = 0;
		for(int i = 0; i < _x.length; i++){
			int v = _x[i].getValue();
			occ[v-_minValue]++;
		}
		//check if _occ and occ is the same
		for(int v = _minValue; v <= _maxValue; v++)
			if(_occ[v-_minValue] != occ[v-_minValue]){
				System.out.println("Alldifferent::verify exception, occ[" + v + "] = " + occ[v-_minValue] + " while _occ[" + v + "] = " + _occ[v-_minValue]);				
				return false;
			}
		int vio = 0;
		for(int v = _minValue; v <= _maxValue; v++){
			int idx = v - _minValue;
			if(_occ[idx] > 1) 
				vio += _occ[idx]-1;
		}
		if(vio != _violations){
			System.out.println("Alldifferent::verify exception, _violations = " + _violations + " while recomputing gets vio = " + vio);
			return false;
		}
			
		return true;
	}

	/**
	 * @param args
	 */
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int n = 10;
		VarInt[] x = new VarInt[n];
		for(int i = 0; i < x.length; i++){
			x[i] = new VarInt(i,1,n);
		}
		Alldifferent c = new Alldifferent(x);
		c.initPropagate();
		System.out.println("Initially: x = [");
		for(int i = 0; i < x.length; i++)
			System.out.print(x[i].getValue() + " ");
		System.out.println("], c.violations = " + c.violations());
		
		Date curDate = new Date();
		long msec = curDate.getTime();
		Random R = new Random(msec);
		int oldV = c.violations();
		for(int it = 1; it <  10000; it++){
			if(c.violations() == 0){
				System.out.println("solution");
				break;
			}
			int idx = R.nextInt(n);
			int val = R.nextInt(n) + 1;
			//System.out.println("Iter " + it + " idx = " + idx + " val = " + val);
			int d = c.getAssignDelta(x[idx], val);
			c.propagateInt(x[idx], val);
			x[idx].setValue(val);
			System.out.print("Iter " + it + ": ");
			for(int i = 0; i < x.length; i++)
				System.out.print(x[i].getValue() + " ");
			System.out.println("assign x[" + idx + "] = " + val + " delta = " + d + " violations = " + c.violations());
			if(oldV + d != c.violations()){
				System.out.println("exception, oldV = " + oldV + " delta = " + d + " newV = " + c.violations());
				assert(false);
			}
			if(!c.verify()){
				System.out.println("c.verify failed");
				assert(false);
			}
			oldV = c.violations();
		}
		
		
	}

}
